/**
 * @file scu/scucpc/2022/b/main
 * @brief
 * @see
 * @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
 * @copyright 2022
 * @date 5/20/2022 12:14:48
 **/

#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = (a); i < (ll)(b); ++i)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
const ll INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
ll m, n, k;
vector<ll> now;

void factor(ll x) {
  int m = sqrt(x);
  for (int i = 2; i <= m; ++i) {
    if (x % i == 0) now.push_back(i);
    while (x % i == 0) x /= i;
  }
}

// x 包含 k 个与 m, n 不互质的数
int count(ll x) {
  ll sz = now.size();
  ll divided = 0;
  for (ll S = 1; S < (1 << sz); ++S) {
    ll pow = __builtin_popcount(S);
    ll base = 1;
    for (ll i = 0; i < sz; ++i) {
      if (S & (1 << i)) base *= now[i];
    }
    divided += x / base * (pow & 1 ? 1 : -1);
  }
  return divided;
}

int bf(int m, int n, int x) {
  int cnt = 0;
  for (int i = 1; i <= x; ++i) {
    if (__gcd(i, m) == 1 && __gcd(i, n) == 1)
      ;
    else
      cnt++;
  }
  return cnt;
}

bool is_coprime(ll x) {
  for (auto el : now) {
    if (x % el == 0) return false;
  }
  return true;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ll tc;
  cin >> tc;
  for (ll _t = 1; _t <= tc; ++_t) {
    cin >> m >> n >> k;
    now.clear();
    factor(m), factor(n);
    ll l = 1, r = 1e9 + 10;

    //    for (int x = 1; x <= 1000; ++x) {
    //      int a = count(x);
    //      int b = bf(m, n, x);
    //      cout << a << ' ' << b << ' ';
    //      if (a != b) cout << "No" << endl;
    //    }

    while (l < r) {
      ll mid = (l + r) / 2;
      if (mid - count(mid) >= k)
        r = mid;
      else
        l = mid + 1;
    }
    ll ans = l;
    for (ll i = 0; i < ans; ++i) {
      if (is_coprime(ans - i)) {
        ans = ans - i;
        break;
      }
    }

    cout << "Case " << _t << ": " << ans << endl;
  }
}
